/*factN2pf.cpp by K.Tsuru */
// since ver 2.181
#ifndef TOOLS_H
#include "tools.h"
#endif  // TOOLS_H

/***************************************************
It evaluates
   N    N     N         N
p= - + --- + --- +...+ ---
   m   m^2   m^3       m^k
This is the exponent of m factorizing N into prime factor as
N = ...(m^p)...

long(32 bits) version causes overflow error in 2nd term
for example
m = 128461
m^2 = 16502228521 > LONG_MAX = 2147483647
Then it needs (*) statement.
****************************************************/
static const int SQRT_INT_MAX = (int)floor(sqrt((double)INT_MAX)); // = 46340 = sqrt(2147483647) its square is 2147395600
static int powerOf(const int N, const int m) {
    if(m > SQRT_INT_MAX) return (N/m);  // (*)

    int d = m, p = 0;

    while(N >= d) {
        p += N/d;   d *= m;
    }
    return p;
}
/*********************************
N! factorization into prime factor
N! = a^p b^q c^r ...x y z
Returns the size of pf[].
**********************************/
int FactorialIntoPrimeFactor(ulong N, SNBlock <primeFactor>& pf) {
    NCBlock <ulong> P;
    int ts = MakePrimeTable(P, N);  // table size

    pf.size( ts, 0);    // allocate memory
    int c;
    for(c = 0; P(c) > 0; c++) {
        ulong t = P(c);
        pf[c].prime = t;
        pf[c].power = powerOf(N, t);
    }
    pf.reserve(c);
    pf[c].prime = 1;
    pf[c].power = 0;
    return c;
}